package com.kevin.Code.Greedy;

/**
 * @author Vinlee Xiao
 * @Classname JumpGameii
 * @Description Leetcode 45. 跳跃游戏 II 中等难度 贪心算法  运用贪心的思想
 * @Date 2021/9/30 11:06
 * @Version 1.0
 */
public class JumpGameii {

    int jumpTimes = Integer.MAX_VALUE;

    public int jump(int[] nums) {

        int len = nums.length;

        help(nums, 0, 0, len);
        return jumpTimes == Integer.MAX_VALUE ? 0 : jumpTimes;
    }


    /**
     * @param nums
     * @param index
     * @param preStep
     * @param len
     */
    public void dfs(int[] nums, int index, int preStep, int len) {

        if (index > len - 1) {
            return;
        }

        if (index >= len - 1) {
            jumpTimes = Math.min(jumpTimes, preStep);
            return;
        }

        for (int i = index; i < len && i < index + nums[index]; i++) {

            dfs(nums, i + 1, preStep + 1, len);
        }


    }


    public void help(int[] nums, int index, int preStep, int len) {


        if (index >= len - 1) {
            jumpTimes = Math.min(jumpTimes, preStep);
            return;
        }

        if (index < len) {
            if (nums[index] == 0) {
                dfs(nums, index - 1, preStep - 1, len);
            } else {
                dfs(nums, index + nums[index], preStep + 1, len);
            }

        }


    }


    /**
     * @param nums
     * @return
     */
    public int jump1(int[] nums) {

        int len = nums.length;
        int position = len - 1;

        int steps = 0;
        //找到离最后一个目标最近的坐标 然后改变坐标找到离该坐标最近的上一个坐标
        while (position > 0) {

            for (int i = 0; i < position; i++) {

                if (i + nums[i] >= position) {
                    steps++;
                    position = i;
//                    System.out.println(position);
                    break;
                }
            }
        }

        return steps;
    }


    /**
     * @param nums
     * @return
     */
    public int jump2(int[] nums) {

        int len = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;

        for (int i = 0; i < len - 1; i++) {

            maxPosition = Math.max(maxPosition, nums[i] + i);

            if (i == end) {
                steps++;
                end = maxPosition;
            }
        }

        return steps;
    }


    /**
     * 超过时间限制
     *
     * @param args
     */
    public static void main(String[] args) {

        JumpGameii jumpGameii = new JumpGameii();
        int[] nums = new int[]{2, 3, 1, 1, 4};
        int i = jumpGameii.jump2(nums);
        System.out.println(i);
    }

}
